package gold.digger;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC1477 {

    /*
    * @param 此题目直接用别人代码，自己只理解思想
    * @return:
    */
    public int minSumOfLengths(int[] arr, int target) {
        // 滑动窗口：先求出所有满足 target 的下标对
        List<int[]> res = new ArrayList<>();

        int i = 0, j = 0;
        int sum = 0;
        while (j < arr.length) {
            sum += arr[j++];
            if (sum < target) continue;
            while (sum > target) sum -= arr[i++];
            if (sum == target) {
                res.add(new int[]{i, j});
            }
        }
        if (res.size() < 2) return -1;

        // 将 res 按照区间长度进行排序
        Collections.sort(res, (o1, o2) -> (len(o1)) - (len(o2)));

        int ans = Integer.MAX_VALUE;
        for (int index = 0; index < res.size() - 1; index++) {
            int[] a1 = res.get(index);
            if ((len(a1)) * 2 >= ans) break;
            for (int k = index + 1; k < res.size(); k++) {
                int[] a2 = res.get(k);
                if (a2[0] >= a1[1] || a2[1] <= a1[0]) {
                    ans = Math.min(ans, len(a1) + len(a2));
                    break;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    // 表示半开半闭区间 [a[0], a[1]) 的长度
    private int len(int[] a) {
        return a[1] - a[0];
    }


    public static void main(String[] args) {
        LC1477 an = new LC1477();
//        int[] arr = {1, 3, 0, 1, 2, 3, 5, 4, 7};
        int[] arr = {1, 3, 5, 7};
        System.out.println(an.minSumOfLengths(arr, 3));
    }
}
